#include "thread.h"

extern func_BiTree fBiTree;

/**
 *  功 能：
 *      线索化二叉树 -- 利用空左指针域
 *  参 数：
 *      root：要线索化的树的根节点
 *      ptmp：临时变量，用于保留前驱节点
 *  返回值：
 *      无
 **/
void thread_lchild(BiTNode *root, BiTNode **ptmp)
{
    if ((root != NULL) && (ptmp != NULL))
    {
        if (*ptmp != NULL)
        {
            (*ptmp)->lchild = root;
            *ptmp = NULL;
        }

        if (root->lchild == NULL)
        {
            *ptmp = root;
        }

        thread_lchild(root->lchild, ptmp);
        thread_lchild(root->rchild, ptmp);
    }
}

/**
 *  功 能：
 *      遍历利用空左指针域线索化二叉树 
 *  参 数：
 *      root：要遍历的线索二叉树的根节点
 *  返回值：
 *      无
 **/
void thread_lchild_print(BiTNode *root)
{
    while (root != NULL)
    {
        printf("%c ", root->data);
        root = root->lchild;
    }
    printf("\n");
}

/**
 *  功 能：
 *      线索化二叉树 -- 利用顺序表
 *  参 数：
 *      root：要线索化的树的根节点
 *      list：顺序表的操作句柄
 *  返回值：
 *      无
 **/
void thread_seqlist(BiTNode *root, seqList *list)
{
    if ((root != NULL) && (list != NULL))
    {
        fSeqList.insert(list, (ListNode *)root, fSeqList.length(list));

        thread_seqlist(root->lchild, list);
        thread_seqlist(root->rchild, list);
    }
}

/**
 *  功 能：
 *      遍历利用顺序表线索化二叉树
 *  参 数：
 *      list：顺序表的操作句柄
 *  返回值：
 *      无
 **/
void thread_seqlist_print(seqList *list)
{
    int i;
    for (i = 0; i < fSeqList.length(list); i++)
    {
        BiTNode *tmp = (BiTNode *)fSeqList.get(list, i);
        printf("%c ", tmp->data);
    }

    printf("\n");
}

/**
 *  链表的节点结构定义
 **/
typedef struct __tag_BiTNode_Thread
{
    LinkListNode Header;
    BiTNode *root;
} TBiTNodeThread;

/**
 *  功 能：
 *      线索化二叉树 -- 利用顺序表
 *  参 数：
 *      root：要线索化的树的根节点
 *      list：顺序表的操作句柄
 *  返回值：
 *      无
 **/
void thread_linklist(BiTNode *root, linkList *list)
{
    if ((root != NULL) && (list != NULL))
    {
        TBiTNodeThread *tmp = malloc(sizeof(TBiTNodeThread));
        /* 将节点的地址赋值给临时节点 */
        tmp->root = root;

        flinklist.insert(list, (LinkListNode *)tmp, flinklist.length(list));
        thread_linklist(root->lchild, list);
        thread_linklist(root->rchild, list);
    }
}
/**
 *  功 能：
 *      遍历利用顺序表线索化二叉树
 *  参 数：
 *      list：顺序表的操作句柄
 *  返回值：
 *      无
 **/
void thread_linklist_print(linkList *list)
{
    int i;
    for (i = 0; i < flinklist.length(list); i++)
    {
        TBiTNodeThread *tmp = (TBiTNodeThread *)flinklist.getNode(list, i);
        printf("%c ", tmp->root->data);
    }

    printf("\n");
}

funThread fthread = {
    thread_lchild,
    thread_seqlist,
    thread_linklist,
    thread_lchild_print,
    thread_seqlist_print,
    thread_linklist_print};
